CODE 31. Binary Tree Level Order Traversal

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 31 Binary Tree Level Order Traversal/

访问原文「CODE 31. Binary Tree Level Order Traversal」

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return new ArrayList<ArrayList<Integer>>();
	}
	ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	ArrayList<Integer> layerVals = new ArrayList<Integer>();
	queue.offer(root);
	int layerNumber = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerVals.add(node.val);
		layerNumber--;
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}

		if (layerNumber == 0) {
			layerNumber = queue.size();
			ArrayList<Integer> layerValsCpy = new ArrayList<Integer>();
			layerValsCpy.addAll(layerVals);
			results.add(layerValsCpy);
			layerVals.clear();
		}
	}
	return results;
}